#include <stdio.h>
// wezly
typedef int node; // typ info dla elementu
void nodestab_print(node* , int , int );
#define NODES_NR 64

// sortowanie
#define key(A) (A) // wyznaczony klucz
#define less(A, B) (key(A) < key(B)) // porownywanie kluczy
#define exch(A, B) { node t = A; A = B; B = t; } // zamiana wezlow
#define compexch(A, B) if (less(B, A)) exch(A, B) // zamiana z porownaniem
#define q 2
#define m 256
#define BYTE_PER_WORD 4
#define bin(A) l+count[A]
#define alpha 0

unsigned getbits(unsigned , int , int );
unsigned digit(node , int );
void msdrsort(node* , int , int , int );

int main() 
{
  node nodestab[] = {1, 34, 10, 6, 8, 18, 5, 7, 23, 15}; // tablica elementow
  int nnr = sizeof nodestab / sizeof(node ); // liczba elementow
  msdrsort(nodestab, 0, nnr, 1); // sortowanie
  //nodestab_print(nodestab, 0, nnr); // wydruk
  return 0;
}

// funkcje dla wezlow
void nodestab_print(node a[], int l, int r)
{
  int i;
  for (i = l; i < r; i++)
    printf("%i ", a[i]);
  printf("\n");
}

// funkcje dla sortowania
unsigned getbits(unsigned x, int p, int n)
{
  return (x>>(p+1-n))&~(~0<<n);
}

unsigned digit(node a, int d)
{
  return getbits(key(a)-alpha, d, 1);
}

void insertion(node a[], int l, int r)
{
  int i, j;
  node v;
  for (i = l + 1; i < r; i++) 
    compexch(a[l], a[i]);
  for (i = l + 2; i < r; i++) { 
    j = i; 
    v = a[i]; 
    while (less(v, a[j-1]))
      { a[j] = a[j-1]; j--; }
    a[j] = v; 
  }  
}

void msdrsort(node a[], int l, int r, int w)
{ 
  int i, j, count[q+1]; 
  node aux[NODES_NR];
  if (w > BYTE_PER_WORD) 
    return;
  if (r-l <= m) { 
    insertion(a, l, r); 
    return; 
  }
  for (j = 0; j < q; j++) 
    count[j] = 0;
  for (i = l; i <= r; i++) 
    count[digit(a[i], w) + 1]++;
  for (j = 1; j < q; j++) 
    count[j] += count[j-1];
  for (i = l; i <= r; i++) 
    aux[l+count[digit(a[i], w)]++] = a[i];
  for (i = l; i <= r; i++) 
    a[i] = aux[i];
  msdrsort(a, l, bin(0)-1, w+1);
  for (j = 0; j < q-1; j++)
    msdrsort(a, bin(j), bin(j+1)-1, w+1);
}
